package ThirtySeventhDay;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class AllPathsSourceTarget {
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> list= new ArrayList<>();
        int n = graph.length - 1;
        dfs(graph,0,res,list,n);
        return res;
    }
    public void dfs(int[][] graph,int num,List<List<Integer>> res,List<Integer> list,int n){
        list.add(num);
        if(num == n){
            res.add(new ArrayList<>(list));
            return;
        }
        int[] arr = graph[num];
        for(int i = 0; i < arr.length; i++){
            dfs(graph,arr[i],res,list,n);
            list.remove(list.size()-1);
        }
    }
}
